package sort.quickSort;

/**
 * @Author: zhang
 * @Description:快排递归
 * @Date: Created in 0:33 2019/9/20
 */
public class quickSortTest {
    public static void main(String[] args) {
        /*int[] arrays = new int[100];
        Random random = new Random();
        for(int i = 0;i<arrays.length;i++){
            arrays[i] = random.nextInt()%100;
        }*/
        int[] arrays = new int[]{5, 1, 7, 4, 8, 9, 2, 3, 6, 0};
        quickSort(arrays, 0, arrays.length - 1);
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + " ");
        }
    }

    //快速排序-递归实现
    public static void quickSort(int[] a, int low, int high) {
        //已经排序完成
        if (low >= high) {
            return;
        }
        //找基准
        int pivotIndex = partition(a, low, high);
        //左边有两个元素以上开始递归
        if (pivotIndex > low + 1) {
            quickSort(a, low, pivotIndex - 1);
        }
        //右边有两个元素以上开始递归
        if (pivotIndex < high - 1) {
            quickSort(a, pivotIndex + 1, high);
        }
    }

    public static int partition(int[] a, int left, int right) {
        int pivot = a[left];
        while (left < right) {
            //从后向前找比基准小的值
            while (left < right && a[right] >= pivot) {
                right--;
            }
            a[left] = a[right];
            //从前向后找比基准大的值
            while (left < right && a[left] <= pivot) {
                left++;
            }
            a[right] = a[left];
        }
        //把基准放回数组中
        a[left] = pivot;
        //返回基准的下标
        return left;
    }
}
